package day69_924;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author clockTown
 * @Date 2021/7/17 19:17
 * @Version 1.0
 */
public class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        int[] colors = new int[n];
        // -1 代表没有染色
        Arrays.fill(colors, -1);
        int COLOR = 0;
        // 深度优先搜索去把图中节点进行染色
        for (int i = 0; i < n; ++i) {
            if (colors[i] == -1) dfs(graph, colors, i, COLOR++);
        }

        // 统计每一种颜色有多少个节点，也就是计算每一个连通分量的大小
        // 给颜色，还颜色数量
        int[] count = new int[COLOR];
        for (int color : colors) count[color]++;

        // 统计每一个初始被感染的计算机有多少个，找到某一个连通分量是只被感染了一个的节点
        int[] colorCount = new int[n];
        for (int node : initial) colorCount[colors[node]]++;

        // 先来找到在被感染的计算机中，去掉一个能够直接去掉一个分量的情况
        int ans = Integer.MAX_VALUE;
        for (int node : initial) {
            int c = colors[node];
            // 当某个被感染的计算机颜色只有一台时，去掉他，就等于去掉了整个连通分量
            if (colorCount[c] == 1) {
                if (ans == Integer.MAX_VALUE) ans = node;
                    // 如果都能直接去掉一个连通分量，就看看谁的连通节点数多，谁多就去掉谁
                else if (count[c] > count[colors[ans]]) ans = node;
                    // 如果两者的连通分量相同，就再看看节点编号是不是更小，取更小的
                else if (count[c] == count[colors[ans]] && node < ans) ans = node;
            }
        }

        // 如果没有那种去掉一个节点就能去掉整个分量的情况，就去掉下标最小的
        if (ans == Integer.MAX_VALUE)
            for (int node :initial) ans = Math.min(ans, node);
        return ans;
    }

    private void dfs(int[][] graph, int[] colors, int node, int color) {
        colors[node] = color;
        // 对 node 的连通节点挨个染上相同颜色
        for (int i = 0; i < graph.length; ++i) {
            if (graph[node][i] == 1 && colors[i] == -1) {
                dfs(graph, colors, i, color);
            }
        }
    }
}
